﻿#define _CRT_SECURE_NO_WARNINGS 1
//给你⼀个字符串s、⼀个字符串t。返回s中涵盖t所有字符的最⼩⼦串。如果s中不存在涵盖t所有字符的⼦串，则返回空字符串""。
//注意：
//对于t中重复字符，我们寻找的⼦字符串中该字符数量必须不少于t中该字符数量。
//如果s中存在这样的⼦串，我们保证它是唯一的答案

//eg：
//输⼊：s = ADOBECODEBANC, t = ABC
//输出：BANC

#include <iostream>
using namespace std;

//思路：滑动窗口+哈希
string minWindow(string s, string t)
{
	int hash1[128] = { 0 };
	// 统计字符串 t 中每⼀个字符的频次
	int kinds = 0;
	// 统计有效字符有多少种
	for (auto ch : t)
		if (hash1[ch]++ == 0) kinds++;
	int hash2[128] = { 0 };
	// 统计窗⼝内每个字符的频次
	int minlen = INT_MAX, begin = -1;
	for (int left = 0, right = 0, count = 0; right < s.size(); right++)
	{
		char in = s[right];
		if (++hash2[in] == hash1[in]) count++;
		// 进窗⼝ + 维护 count
		while (count == kinds)
			// 判断条件
		{
			if (right - left + 1 < minlen)
				// 更新结果
			{
				minlen = right - left + 1;
				begin = left;
			}
			char out = s[left++];
			if (hash2[out]-- == hash1[out]) count--;
			// 出窗⼝ + 维护 count
		}
	}
	if (begin == -1) return "";
	else return s.substr(begin, minlen);
}

int main()
{
	string s("ADOBECODEBANC");
	string t("ABC");
	cout << "s: " << s << "  " << "t: "<<t<<endl;

	string an=minWindow(s, t);
	cout << an << endl;

	return 0;
}